Arithmetic coding process is involved in image coding process. With arithmetic coding, the information entropy of a code symbol sequence is approximated by mapping the sequence to a value within an interval of [0, 1), so as to achieve a desired data compression ratio. During an arithmetic coding process, it is necessary to perform iteration on the current encoding interval according to the probability of each symbol within a set of code symbols. Once this process is complete for the code sequence, an interval corresponding to the whole sequence may be obtained. A value selected from this interval may represent the information of the whole sequence.
The encoding of the arithmetic codes may be divided into two phases: in the first phase, the probability of each source symbol is calculated so as to assign an appropriate symbol interval; and in the second phase, symbols are input and the sequence is encoded. Here, the probabilities of the symbols may be obtained on the basis of a priori knowledge in the first phase of encoding.
The second phase of encoding is an iteration procedure, mainly including:                (1) defining the current interval as [0,1);        (2) for each symbol of the input stream, repeating the following two steps:        
(21) dividing the current interval into sub-intervals having lengths proportional to the probability of the symbol; and
(22) selecting a sub-interval for the current symbol and define it as the current interval; and                (3) processing all the symbols in the above manner, and finally outputting a value uniquely defining the current interval as the coded codeword.        
The above arithmetic coding lies mainly in the iteration process of intervals. The probabilities of the symbols during the iteration process may be determined on basis of a self-adaptive model.
If there are only two symbols of 0 and 1 in the symbol set, the above procedure may be simplified. In this case, the most probable symbol and the least probable symbol are designated abbreviated as MPS and LPS, respectively. If R represents the current interval, Low represents the lower bound of the current interval, pLPS represents the probability of LPS, pMPS represents the probability of MPS, and pLPS+pMPS=1, the above iteration may be given by the following equations:RLPS=R×pLPS,RMPS=R−RLPS;                When encoding LPS, R=RLPS;Low=Low+RMPS;        When encoding MPS, R=R×pMPS=R−RLPS.        
The above equations provide an explanation to the principle of the arithmetic coding method. In practical applications, the above algorithm can not be employed directly due to a limited precision and the implementation complexity of multipliers. In addition, self-adaptive probability estimation is usually used to calculate the probabilities of the symbols so as to improve the coding efficiency of the arithmetic codes.
The presently used arithmetic encoders all employ a renormalization process to solve the problems caused by the limited precision. Various solutions are proposed for the multiply operations, which include: in the arithmetic encoder of Q-Coder applied in the JPEG standard, the multiply operations are avoided by using approximations which limits R in an interval of [0.75, 1.5); and in the arithmetic encoder of CABAC used in the H.264/AVC standard, the multiply operations are avoided with the aid of a look-up table. For the self-adaptive update of the probabilities, the multiply operations may be avoided by using Finite State Machine (FSM) algorithms. Specifically, probability estimation is performed by choosing different jump schemes for MPS and LPS from a state transition table.
Currently, arithmetic encoders performing arithmetic coding in the logarithm domain have also been proposed, and thus the multiply operations may be avoided by mapping from the original domain to the logarithm domain. However, in such an encoder, data conversions between the original domain and the logarithm domain are implemented with a logarithm table and an inverse logarithm table. Probability update is also performed in the original domain by means of a state transition table. With the introduction of those tables, it more storage is required, and the implementation is more complex with the complicated look-up operations. Therefore, it is difficult to implement the solution on a personal computer (PC).